package com.gorkr;

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.Vector;

public class L516 {
    // 状态 dp 转移 basecase
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        char[] c = s.toCharArray();


        int[][] dp = new int[n][n];
        // base case
        for(int i=0; i<n; i++){
            dp[i][i] = 1;  // 长度为1的子序列回文为1
        }  // 以及 i>j的回文为0

        // 状态
        for(int i=n-1;i>=0; i--){// 子序列头
            for(int j=i+1; j<n; j++){ // 子序列尾
                // 状态转移
                if(c[i]==c[j]){
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }

        return dp[0][n-1];

    }
}